package top.datacluster.basic.algorithm.leetcode.dynamic;

public class LeetCode1471 {

    public int waysToStep(int n) {
        int MOD = 1_000_000_007;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (n == 3) {
            return 4;
        }
        long[] dp = new long[3];
        dp[0] = 4;
        dp[1] = 1;
        dp[2] = 2;
        int i = 4;
        while (i <= n) {
            dp[i % 3] = (dp[0] + dp[1] + dp[2]) % MOD;
            i++;
        }
        return (int)dp[n % 3];
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode1471().waysToStep(61));
    }
}
